长序列求和 (longsum) 的题解

题目背景

AC_Automation 作为一个可爱的妹子,她喜欢求和与乘积,还特别喜欢长的东西。现在她给你一个很长的序列,想让你求一些东西。看在她那么可爱的份上,就帮帮她吧。

题目描述

她本来想给你一个很长的序列 AA,但是为了让你解出题目,善良的她给了一个较短的序列 BnB_n 来表示所有在序列 AA 的中的数。具体来讲,序列 AA 和序列 BB 之间的关系为:

A(i1)×n3+(j1)×n2+(k1)×n+l=Bi×Bj+Bk×BlA_{(i - 1) \times n^3 + (j - 1) \times n^2 + (k-1) \times n + l} = B_i \times B_j + B_k \times B_l

(其中 1i,j,k,ln1 \le i, j, k, l \le n

可以发现,序列 AA 的下标在 1n41 \sim n^4 之间。她还定义了一个函数 f(l,r)f(l, r) ,满足:

f(l,r)=i=lrAi=Al+Al+1++Arf(l, r) = \sum_{i = l}^{r}A_i = A_l + A_{l + 1} + \cdots + A_r

现在她给了你一个长度为 nn 的序列 BnB_n ,以及 TT 个询问,对于第 ii 个询问 li,ril_i, r_i ,请你求出对应的 f(li,ri)f(l_i, r_i) 。因为她很讨厌高精度,为了满足她的要求,请你输出该值模上 109+710^9 + 7 的值

由于她太菜了,看在她那么可爱的份上,就帮帮她吧。

输入格式

第一行两个整数 nnTT ,分别表示序列长度和询问的个数

第二行 nn 个正整数 BiB_i ,表示 AC_Automation 给你的一个序列。

接下来 TT 行,每行一个 lil_irir_i ,表示 TT 个询问。

输出格式

TT 行,表示每个 lil_irir_i 所对应的 f(li,ri)f(l_i, r_i) 模上 109+710^9 + 7 的值

样例输入

2 3
1 2
1 8
1 16
9 16

样例输出

30
72
42

样例解释

A1=2,A2=3,A3=3,A4=5A_{1} = 2, A_{2} = 3, A_{3} = 3, A_{4} = 5

A5=3,A6=4,A7=4,A8=6A_{5} = 3, A_{6} = 4, A_{7} = 4, A_{8} = 6

A9=3,A10=4,A11=4,A12=6A_{9} = 3, A_{10} = 4, A_{11} = 4, A_{12} = 6

A13=5,A14=6,A15=6,A16=8A_{13} = 5, A_{14} = 6, A_{15} = 6, A_{16} = 8

f(1,8)=A1+A2+A3+A4+A5+A6+A7+A8=30f(1, 8) = A_{1} + A_{2} + A_{3} + A_{4} + A_{5} + A_{6} + A_{7} + A_{8} = 30

f(1,16)=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13+A14+A15+A16=72f(1, 16) = A_{1} + A_{2} + A_{3} + A_{4} + A_{5} + A_{6} + A_{7} + A_{8}\\ + A_{9} + A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = 72

f(9,16)=A9+A10+A11+A12+A13+A14+A15+A16=42f(9, 16) = A_{9} + A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = 42

数据范围与约定

测试点序号 nn\le TT\le
151 \sim 5 2020 10410^4
6156 \sim 15 10310^3 10410^4
162516 \sim 25 10410^4 2×1052 \times 10^5

对于 100%100\% 的数据,1n1041 \le n \le 10^41lirin41 \le l_i \le r_i \le n^41T2×1051 \le T\le 2 \times 10^51Bi1041 \le B_i \le 10^4

题解

没有前缀和的暴力,得 44 分,有前缀和的暴力,得 2020 分。

我们来考虑如何得到这 6060 分。

可以发现,由于 n2<106n^2 < 10^6 ,所以我们可以写一个 O(n2+T)O(n^2 + T) 的算法。具体来讲,我们可以令一个二维数组 CC ,其中 Cin+j=BiBjC_{i \cdot n + j} = B_i \cdot B_j 。那么 BiBj+BkBl=Cin+j+Ckn+lB_i \cdot B_j + B_k \cdot B_l = C_{i \cdot n + j} + C_{k \cdot n + l}

我们来看这个式子(其中假设 BiBj=CxB_i \cdot B_j = C_xBkBl=CyB_k \cdot B_l = C_y ,且 Ap=BiBj+BkBlA_p = B_i \cdot B_j + B_k \cdot B_l):

p=lrAp=Cx+Cy\sum_{p = l}^{r}A_p = C_x + C_y

具体来讲,每个 ApA_p 所对应的 CxC_xCyC_y 如下图:

假如 n=2,l=2,r=13n = 2, l = 2, r = 13 ,我们就可以有这样的变换:

p=213(Cx+Cy)\sum_{p = 2}^{13} (C_x + C_y)

=(C1+C3)+(C1+C4)+(C2+C1)++(C2+C4)+(C3+C1)++(C3+C4)+(C4+C1)= (C_1 + C_3) + (C_1 + C_4) + (C_2 + C_1) + \cdots + (C_2 + C_4) + (C_3 + C_1) + \cdots + (C_3 + C_4) + (C_4+ C_1)

=2C1+(C3+C4)+4(C2+C3)+2(C1+C2+C3+C4)+C4+C1= 2 \cdot C_1 + (C_3 + C_4) + 4 \cdot (C_2 + C_3) + 2 \cdot (C_1 + C_2 + C_3 + C_4) + C_4 + C_1

我们令 si=p=1iCp,s0=0s_i = \sum^{i}_{p = 1} C_p, s_0 = 0(可以发现这是可以预处理的),那么

=2C1+(s4s2)+4(s3s1)+2s4+C4+(s1s0)= 2 \cdot C_1 + (s_4 - s_2) + 4 \cdot (s_3 - s_1) + 2 \cdot s_4 + C_4 + (s_1 - s_0)

结构如下图:

同样,在 n=2,l=7,r=16n = 2, l = 7, r = 16 的时候,也有这样的变换:

p=213CxCy=1C2+(s4s3)+4(s4s3)+2s4\sum_{p = 2}^{13} C_x \cdot C_y = 1 \cdot C_2 + (s_4 - s_3) + 4 \cdot (s_4 - s_3) + 2 \cdot s_4

结构如下图:

既然这样,那么我们就可以得到做法了:先看 l,rl, r 之间有几个 n2n^2 长度的块,将其求和,再将一些零碎的东西再求和。

好了,这 6060 分的思路都有了,100100 分的思路也不难了吧(也就是把这个长度为 n4n^4 的序列分别分成长度为 nnn2n^2n3n^3 的块,分得细一些,稍稍麻烦一些)。这是我丑陋的代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7.5;
const int N = 10005;
LL B[N], PreSum[N];
int n, T;
inline LL f(LL l, LL r) {
    LL ret = 0ll;
    LL tl = 0, tr = 0;
    tl = (l - 1) / ((LL)(n * n) * (LL)n) + 2;
    tr = (r - 1) / ((LL)(n * n) * (LL)n);
    if (tl <= tr) {
        (ret += (((PreSum[tr] - PreSum[tl - 1]) * PreSum[n]) % mod) * ((n * n) % mod)) %= mod;
        (ret += ((PreSum[n] * PreSum[n]) % mod) * (((tr - tl + 1) * n) % mod)) %= mod;
    }
    tl--; tr++;
    if (tl != tr) {
        LL ttl = (l - 1) / (LL)(n * n) + 2, ttr = tl * n;
        if (ttl <= ttr)
        (ret += ((B[tl] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
        (ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
        ttl = (tr - 1) * n + 1, ttr = (r - 1) / (LL)(n * n);
        if (ttl <= ttr)
        (ret += ((B[tr] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
        (ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
    } else {
        LL ttl = (l - 1) / (LL)(n * n) + 2, ttr = (r - 1) / (LL)(n * n);
        if (ttl <= ttr)
        (ret += ((B[tl] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
        (ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
    }
    LL ttl = (l - 1) / (LL)(n * n) + 1, ttr = (r - 1) / (LL)(n * n) + 1;
    if (ttl != ttr) {
        LL tttl = (l - 1) / n + 2, tttr = ttl * n;
        if (tttl <= tttr)
        (ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
        (ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
        tttl = (ttr - 1) * n + 1, tttr = (r - 1) / n;
        if (tttl <= tttr)
        (ret += ((B[tr] * B[(ttr - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
        (ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
    } else {
        LL tttl = (l - 1) / n + 2, tttr = (r - 1) / n;
        if (tttl <= tttr)
        (ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
        (ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
    }
    LL tttl = (l - 1) / (LL)n + 1, tttr = (r - 1) / (LL)n + 1;
    if (tttl != tttr) {
        LL ttttl = l, ttttr = tttl * n;
        (ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
        (ret += B[(tttl - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
        ttttl = (tttr - 1) * n + 1, ttttr = r;
        (ret += ((B[tr] * B[(ttr - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
        (ret += B[(tttr - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
    } else {
        LL ttttl = l, ttttr = r;
        (ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
        (ret += B[(tttl - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
    }
    return (ret + mod) % mod;
}
int main() {
    scanf("%d%d", &n, &T);
    for (int i = 1; i <= n; i++) scanf("%lld", B + i), PreSum[i] = (PreSum[i - 1] + B[i]) % mod;
    for (LL l, r; T--; ) {
        scanf("%lld%lld", &l, &r);
        if (l > r || l < 1 || l > (LL)n * (LL)n * (LL)n * (LL)n || r < 1 || r > (LL)n * (LL)n * (LL)n * (LL)n) throw 112;
        printf("%lld\n", f(l, r));
    }
    return 0;
}

感谢阅读!